package MainTest;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public static void main(String[] args) {
        ListNode listNode1 = new MainTest.Solution().new ListNode(1);
        ListNode listNode2 = new MainTest.Solution().new ListNode(2);
        ListNode listNode3 = new MainTest.Solution().new ListNode(3);
        ListNode listNode33 = new MainTest.Solution().new ListNode(3);
        ListNode listNode4 = new MainTest.Solution().new ListNode(4);
        ListNode listNode44 = new MainTest.Solution().new ListNode(4);
        ListNode listNode5 = new MainTest.Solution().new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode33;
        listNode33.next = listNode4;
        listNode4.next = listNode44;
        listNode44.next = listNode5;
        ListNode node = new Solution().deleteDuplication(listNode1);
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }

    public ListNode deleteDuplication(ListNode pHead) {
        Set<Integer> allNodeSet = new HashSet<>();
        Set<Integer> shouldDelSet = new HashSet<>();
        ListNode realHead = pHead;
        while (pHead != null) {
            if (allNodeSet.contains(pHead.val)) {
                shouldDelSet.add(pHead.val);
            }
            allNodeSet.add(pHead.val);
            pHead = pHead.next;
        }
        this.deleteIn3Node(null, realHead, shouldDelSet);
        return realHead;
    }

    public void deleteIn3Node(ListNode last, ListNode current, Set<Integer> shouldDelSet) {
        if (current == null) {
            return;
        }
        if (shouldDelSet.contains(current.val)) {
            if (last == null) {
                current = current.next;
            } else {
                last.next = current.next;
            }
            this.deleteIn3Node(last, current.next, shouldDelSet);
        } else {
            this.deleteIn3Node(current, current.next, shouldDelSet);
        }
    }
    public class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }

}
